package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 23. 合并 K 个升序链表
 * @since 2024/2/2 16:18
 */
public class MergeKLists23 {
    // 给你一个链表数组，每个链表都已经按升序排列。
    // 请你将所有链表合并到一个升序链表中，返回合并后的链表。
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return splitAndMerge(lists, 0, lists.length - 1);
    }

    // 递归：分而治之，左右拆分链表集合，直至子集合只有一个链表，返回左右拆分结果，调用合并两个链表的方法
    private ListNode splitAndMerge(ListNode[] lists, int low, int high) {
        // 集合只有一个链表，返回
        if (low == high) {
            return lists[low];
        }

        // 分
        int m = (low + high) >>> 1;
        ListNode left = splitAndMerge(lists, low, m);
        ListNode right = splitAndMerge(lists, m + 1, high);

        // 合：合并两个链表
        return mergeTwoList(left, right);

    }

    // 合并两个有序链表的方法
    private static ListNode mergeTwoList(ListNode list1, ListNode list2) {
        ListNode sentinel = new ListNode(-1, null);
        ListNode p = sentinel;
        // 循环，将两个链表小的节点插入新链表末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            // p 后移
            p = p.next;
        }
        // 将原链表剩余节点链到新链表末尾
        if (list1 != null) {
            p.next = list1;
        } else if (list2 != null) {
            p.next = list2;
        }
        return sentinel.next;
    }
}
